package leetcode;

import common.ListNode;
import common.Util;

/**
 * 单链表实现
 * @link{https://leetcode-cn.com/problems/design-linked-list/}
 */
public class LeetCode707 {
    /**
     * 哨兵头节点
     */
    public ListNode head;
    /**
     * 单链表的大小
     */
    public int size;

    public LeetCode707() {
        this.head = new ListNode(0);
        this.size = 0;
    }

    /**
     * Get the value of the index-th node in the linked list. If the index is
     * invalid, return -1.
     */
    public int get(int index) {
        if (index < 0 || size == 0 || index > size - 1) return -1;
        ListNode cur = head.next;
        for (int i = 0; i < index; i++) cur = cur.next;
        return cur.val;
    }

    /**
     * Add a node of value val before the first element of the linked list. After
     * the insertion, the new node will be the first node of the linked list.
     */
    public void addAtHead(int val) {
        ListNode toAddNode = new ListNode(val);
        ListNode next = this.head.next;
        this.head.next = toAddNode;
        toAddNode.next = next;
        this.size++;
    }

    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
        ListNode toAddNode = new ListNode(val);
        ListNode temp = head;
        while (temp.next != null) temp = temp.next;
        temp.next = toAddNode;
        this.size++;
    }

    /**
     * Add a node of value val before the index-th node in the linked list. If index
     * equals to the length of linked list, the node will be appended to the end of
     * linked list. If index is greater than the length, the node will not be
     * inserted.
     */
    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) return;
        ListNode toAddNode = new ListNode(val);
        ListNode prev = head;
        for (int i = 0; i < index; i++) prev = prev.next;
        toAddNode.next = prev.next;
        prev.next = toAddNode;
        this.size++;
    }

    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        if (index < 0 || size == 0 || index > size - 1) return;
        ListNode prev = head;
        for (int i = 0; i < index; i++) prev = prev.next;
        prev.next = prev.next.next;
        this.size--;
    }
    public static void main(String[] args) {
        LeetCode707 linkedList = new LeetCode707();
        linkedList.addAtHead(1);
        System.out.println(Util.formatListNode(linkedList.head));
        linkedList.addAtTail(3);
        System.out.println(Util.formatListNode(linkedList.head));
        linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
        System.out.println(Util.formatListNode(linkedList.head));
        linkedList.get(1);            //返回2
        linkedList.deleteAtIndex(1);  //现在链表是1-> 3
        System.out.println(Util.formatListNode(linkedList.head));
        linkedList.get(1);

    }
}